package sort.quicksort.improve;

import org.junit.Test;

import java.util.Random;

public class QuickSort {
    private final static Random random = new Random(System.currentTimeMillis()); //随机数

    @Test
    public void test() {
//        System.out.println(random.nextInt(100));
//        int[] a = {6, 1, 2, 7, 9, 3, 4, 5, 8};
//        int[] a = {5, 1, 1, 2, 0, 0};
        int[] a = {5, 2, 3, 1};
//        int[] a = {1,2,3,4,4,4,5,6,7};
//        sort(a, 0, a.length - 1);
        sortArray(a);
        for (int num : a) {
            System.out.print(num + " ");
        }
    }

    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1); // ******** 别写成 nums.length
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        // *** error: left > right 一定要加上 等于号
        if (left >= right) {
            return;
        }

        int pivotIndex = partiton_2(nums, left, right);
        quickSort(nums, left, pivotIndex - 1); //别写成 partiton(nums, left, pivotIndex - 1)！！！
        quickSort(nums, pivotIndex + 1, right);
    }

    //     [left+1,j] <=pivot
    //     (j,i)>pivot
    //    单路快排
    private int partiton(int[] nums, int left, int right) {
        int randomIndex = left + random.nextInt(right - left + 1); // 产生[left,right]的某个索引
        swap(nums, left, randomIndex);

        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) { // <=
            if (nums[i] <= pivot) {     //将大于pivot的数值往后挤
                j++;
                swap(nums, i, j);
            }
        }
        swap(nums, left, j); //j+1已经大于pivot，不能将其交换到left处
        return j;
    }

    // 双路快排
    private int partiton_2(int[] nums, int left, int right) {
        // 产生[left,right]的某个索引
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex);

        int pivot = nums[left];
        int le = left + 1; // ***
        int ge = right;    // 不要写成 ge = left + 1 ..

        // [left+1,le) <= pivot
        // (ge,right] >= pivot
        while (true) {
            //*** 这里不写成while(le<ge)是为了防止 le>=ge的时候里面还在判断，就会出现越界问题；应该让它们各自移动，然后判断是否超过了

            // le <= ge (错误写法!: le<ge)
            // le <= ge && nums[le]<pivot 这两个条件不能颠倒
            while (le <= ge && nums[le] < pivot) { //必须是严格小于
                le++;
            }

            // le <= ge ***
            // 必须是严格大于
            while (le <= ge && nums[ge] > pivot) {
                ge--;
            }

            // le来到了一个大于等于pivot的位置
            // ge来到了一个小于等于pivot的位置
            if (le >= ge) {
                //如果le==ge,那么对应的值就是等于pivot，此时就可以退出循环了
                break;
            }
            swap(nums, le, ge);
            le++;
            ge--;
        }
        swap(nums, left, ge); // ***
        return ge;
    }

    //三路快排
    private void quickSort_3(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int randomIndex = left + random.nextInt(right - left + 1); // 产生[left,right]的某个索引
        swap(nums, left, randomIndex);
        int pivot = nums[left];

        //三个指针
        int lt = left + 1;
        int gt = right;
        int i = left + 1;

//        [left+1,lt) < pivot
//        [lt,i) == pivot
//        (gt,right] > pivot
        while (i <= gt) { //当i==gt的时，第二个区间和第三个区间还没连起来，所以循环还应该继续,即nums[i]位置的元素还没归入区间内
            if (nums[i] < pivot) {
                //交换前lt指向的元素值等于pivot，交换到i位置后不需要再做判断，所以直接i++
                swap(nums, i, lt);         //将小于pivot的值放到 [left+1,lt)这个区间里面
                lt++;
                i++;  //
            } else if (nums[i] == pivot) {
                i++;
            } else {
                swap(nums, i, gt);
                gt--;
            }
        }

        swap(nums, left, lt - 1);
        quickSort_3(nums, left, lt - 2);
        quickSort_3(nums, gt + 1, right);
    }


    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}